package com.yun.algorithm.sort;


import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/*
    单边循环快排(lomuto 洛穆托分区方案)
    核心思想：每轮找到一个基准点袁术，把比它小的放到它左边，比它大的放到它右边，这称为分区

 */
public class QuickSortLomuto {

    public static void sort(int[] a) {
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a, left, right);
        quick(a, left, p - 1);
        quick(a, p + 1, right);
    }

    private static int partition(int[] a, int left, int right) {
        int pv = a[right];//基准点元素值
        int i = left;
        int j = left;
        while (j < right) {
            if (a[j] < pv) {//j 找到比基准点小的元素
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
            }
            j++;
        }
        swap(a, i, right);
        return i;
    }

    //随机基准点
    private static int partition1(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(a, idx, left);
        int pv = a[left];//基准点元素值
        int i = left + 1;
        int j = right;
        while (i <= j) {
            //1.j从右向左找小的
            while (i <= j && a[i] < pv) {
                i++;
            }
            //2.i从左向右找大的
            while (i <= j && a[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(a, i, j);
                i++;
                j--;
            }
        }
        swap(a, j, left);
        return j;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 3, 4, 2, 1};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
